package job._20240327meituan;

import util.TreeNode;

/**
 * @Project : algorithm-learning-java
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/3/27 15:01
 */
public class Q1 {
    public static TreeNode createTreeByPreorderAndInorder(int[] preorder, int[] inorder) {
        return preorderAndInorderCreateTree(preorder, inorder, 0, preorder.length - 1, 0, preorder.length - 1);
    }

    private static TreeNode preorderAndInorderCreateTree(int[] preorder, int[] inorder, int l1, int r1, int l2, int r2) {
        if (l1 > r1) return null;
        TreeNode node = new TreeNode(preorder[l1]);
        int k = l2;
        for (; k <= r2; k++) {
            if (inorder[k] == node.val) break;
        }
        node.left = preorderAndInorderCreateTree(preorder, inorder, l1 + 1, l1 + k - l2, l2, k - 1);
        node.right = preorderAndInorderCreateTree(preorder, inorder, l1 + k - l2 + 1, r1, k + 1, r2);
        return node;
    }

    static int res = 0;

    static void dfs(TreeNode node, int k, int x) {
        if (node == null) return;
        if (k == x) res++;
        dfs(node.left, k + 1, x);
        dfs(node.right, k + 1, x);
    }

    public static void main(String[] args) {
        TreeNode root = Q1.createTreeByPreorderAndInorder(new int[]{1, 2, 4, 5, 3, 6, 7}, new int[]{4, 2, 5, 1, 6, 3, 7});
        dfs(root, 1, 3);
        System.out.println(res);
    }
}
